package offerbook;

import utils.TreeNode;
import utils.TreeUtil;


/**
 * 输入一个BST后续遍历的数组，重建BST
 * 递归分析思路同 {@link Code06_ReConstructBT_二叉树重建}
 * @date 2020/3/9 16:24
 */
public class Code24_ReconstructBST {
    public static TreeNode reconstruct(int [] sequence) {
        if(sequence == null || sequence.length == 0) return null;
        return process(sequence,0,sequence.length-1);
    }

    private static TreeNode process(int[] sequence, int start, int end) {
        /**
         * {@link Code06_ReConstructBT}  相同的递归思想
         *
         * base case1 ：
         * 最后只剩下两个元素，
         *  如{2,4}, 2<4  start = 1,split = 2 ,end = split -1 ,递归左子树start = end，
         *  递归右子树start = split= 2 , end = end - 1 = 1 ,start > end
         *
         *  如{5,4},5>4 ,start = split = 1, end = split-1 = 0, 递归左子树start = 1,end = 0,start>end
         *  递归右子树,start = 1,end = 1 ,start = end
         */
        if(start > end) return null;
        if(start == end) return new TreeNode(sequence[start]);
        //因为是后续遍历，最后的值一定是根节点
        int rootVal = sequence[end];
        TreeNode root = new TreeNode(rootVal);
        int split = start;
        //root的左子树，所有的值都比root值小
        for(;split < end && sequence[split] < rootVal; split++);
        //root的右子树
        for (int i = split;i < end;i++){
            //如果右子树有比root值小的，给的非法
            if(sequence[i] < rootVal) throw new RuntimeException("illegal");
        }
        root.left = process(sequence,start,split-1);
        root.right = process(sequence,split,end-1);
        return root;

    }

    public static void main(String[] args) {
        int[]arr = {5,7,6,9,11,10,8};
        TreeNode treeNode = reconstruct(arr);
        TreeUtil.printTree(treeNode);
    }
}
